Data such as letters, numbers, and words are often maintained and stored in different types of data structures that complement their eventual with an application program. Since a List data structure enables the storing of data objects in an ordered set, this data structure is typically employed with an application program that often retrieves several sequentially related data objects at a time. For example, a multi-media player program usually generates streaming video from sequentially ordered data objects in a List data structure. Although retrieval times for large numbers of sequentially ordered or related data objects can be improved by the use of a List data structure, it may not always be the optimal data structure for retrieving individual and/or several non-sequential or unrelated data objects from a large set of data objects. It is well known that the maximum amount of time to locate an individual data object on a list increases as the number of data objects referenced by the list increase.
Another type of data structure is the Trie, which is often used with an application program that requests individual and/or several non-sequential or unrelated data objects. A Trie stores data in each transition between each node in a multi-level data structure, rather than at the node itself. In this way, all of the transitions in the path between the root and each leaf represent the data object (key) and each transition between each node in the path is associated with a single character/number of the key. Since the nodes themselves are unlabeled, each transition between each node is labeled with a particular character/number. Also, the Trie data structure facilitates the calculation of a constant maximum amount of time to retrieve a stored data object based on the number of levels (nodes associated with the number of alphanumeric characters in the longest data object) in the Trie, e.g., O (1). Thus, the maximum search time for a given number of levels in a Trie data structure remains relatively constant as the actual number of data objects stored in the data structure increases.
For example, a dictionary program often employs a Trie data structure to store words and provide relatively constant maximum search times as the number of words (but not their length) in the dictionary increase. In a Trie data structure for a dictionary program, every character in the alphabet (A through Z) is partitioned into individual and disjoint main level search nodes. Also, the total number of search node levels in a Trie data structure for a dictionary corresponds to the number of characters in the dictionary's longest possible word.
Although the List and Trie data structures can complement the operation of particular application programs, there are many other types of application programs that can generate requests for both individual/unrelated and sequential/related data objects. A facility that could employ a particular request generated by an application program to choose a type of data structure most suited to reference and retrieve requested data would be an improvement over the prior art. Also, a data structure that could provide access by one or more unique keys to the same data and enable the automatic removal of all references to deleted data would complement the operation of application programs that generate different types of requests.
A more complete appreciation of the invention and its improvements can be obtained by reference to the accompanying drawings, which are briefly summarized below, to the following detail description of presently preferred embodiments of the invention, and to the appended claims.